#include "temu.h"
#define max(a,b) ((a)>(b)?(a):(b))
/* We use the POSIX regex functions to process regular expressions.
 * Type 'man regex' for more information about POSIX regex functions.
 */
#include <sys/types.h>
#include <regex.h>

enum {
	NOTYPE = 256, // 无类型（默认类型）
	EQ = 1,           // 等于运算符
	NUM = 2 ,       // 十进制数字
	HEXNUM = 3,    // 十六进制数字
	REGNAME = 4,    //寄存器名称
	NOTEQ = 5,        //不相等
	AND = 6,           // & 
	OR = 7,             // |
	NEG = 8,         // 取反
	DEREF = 9,       // 指针
	//'+',         // 加法运算符
	//'-',        // 减法运算符
	//'*',         // 乘法运算符
	//'/',          // 除法运算符
	//'(',       // 左括号
	//')',       // 右括号
	//'!'
	/* TODO: Add more token types */


};



static struct rule {
	char *regex;
	int token_type;
} rules[] = {

	/* TODO: Add more rules.
	 * Pay attention to the precedence level of different rules.
	 */

	{" +",	NOTYPE},				// spaces
	{"\\=\\=", EQ},						// equal
	{"\\!\\=",NOTEQ},
	{"\\&\\&",AND},
	{"\\|\\|",OR},
	{"0[xX][0-9a-fA-F]+", HEXNUM}, //十六进制
	{"[0-9]+", NUM}, //十进制
	{"\\$[a-zA-Z]*[0-9]*",REGNAME}, //寄存器

	{"\\+", '+'},					// plus
	{"\\-",'-'},
	{"\\*",'*'},
	{"\\/",'/'},
	{"\\(",'('},
	{"\\)",')'},
	{"\\!",'!'}

};

#define NR_REGEX (sizeof(rules) / sizeof(rules[0]) )

static regex_t re[NR_REGEX];

/* Rules are used for many times.
 * Therefore we compile them only once before any usage.
 */
void init_regex() {
	int i;
	char error_msg[128];
	int ret;

	for(i = 0; i < NR_REGEX; i ++) {
		ret = regcomp(&re[i], rules[i].regex, REG_EXTENDED);
		if(ret != 0) {
			regerror(ret, &re[i], error_msg, 128);
			Assert(ret == 0, "regex compilation failed: %s\n%s", error_msg, rules[i].regex);
		}
	}
}

typedef struct token {
	int type;
	char str[32];
} Token;

Token tokens[32];
int nr_token;

static bool make_token(char *e) {
	int position = 0;
	int i;
	regmatch_t pmatch;
	
	nr_token = 0;

	while(e[position] != '\0') {
		/* Try all rules one by one. */
		for(i = 0; i < NR_REGEX; i ++) {
			if(regexec(&re[i], e + position, 1, &pmatch, 0) == 0 && pmatch.rm_so == 0) {
				char *substr_start = e + position;
				int substr_len = pmatch.rm_eo;

				Log("match rules[%d] = \"%s\" at position %d with len %d: %.*s", i, rules[i].regex, position, substr_len, substr_len, substr_start);
				position += substr_len;

				/* TODO: Now a new token is recognized with rules[i]. Add codes
				 * to record the token in the array `tokens'. For certain types
				 * of tokens, some extra actions should be performed.
				 */

				Token temp;
				switch(rules[i].token_type) {
					case '+':
						temp.type = '+';
						tokens[nr_token] = temp;
						nr_token++;
						break;
					case '-':
						temp.type = '-';
						tokens[nr_token] = temp;
						nr_token++;
						break;
					case '*':
						temp.type = '*';
						tokens[nr_token] = temp;
						nr_token++;
						break;
					case '/':
						temp.type = '/';
						tokens[nr_token] = temp;
						nr_token++;
						break;
					case '(':
						temp.type = '(';
						tokens[nr_token] = temp;
						nr_token++;
						break;
					case ')' :
						temp.type = ')';
						tokens[nr_token] = temp;
						nr_token++;
						break;
					case '!':
						temp.type = '!';
						tokens[nr_token] = temp;
						nr_token++;
						break;
					case 256:       //NOTYPE
						break;
					case 1:         //EQ
						tokens[nr_token].type = 1;
						strcpy(tokens[nr_token].str, "=="); 
						nr_token++;
						break;
					case 2:         //NUMBER
						tokens[nr_token].type = 2;
						strncpy(tokens[nr_token].str, &e[position - substr_len], substr_len);//使用strncpy防止发生溢出
						nr_token++;
						break;
					case 3:         //HEXNUMBER
						tokens[nr_token].type = 3;
						strncpy(tokens[nr_token].str, &e[position - substr_len], substr_len);
						nr_token++;
						break;
					case 4:       //REGNAME
						tokens[nr_token].type = 4;
						strncpy(tokens[nr_token].str, &e[position - substr_len], substr_len);
						nr_token++;
						break;
					case 5:      //NOTEQ
						tokens[nr_token].type = 5;
						strcpy(tokens[nr_token].str, "!=");
						nr_token++;
						break;
					case 6:      //AND
						tokens[nr_token].type = 6;
						strcpy(tokens[nr_token].str, "&&");
						nr_token++;
						break;
					case 7:      //OR
						tokens[nr_token].type = 7;
						strcpy(tokens[nr_token].str, "||");
						nr_token++;
						break;
					default: panic("Unknown token type");
				}

				break;
			}
		}

		if(i == NR_REGEX) {
			printf("no match at position %d\n%s\n%*.s^\n", position, e, position, "");
			return false;
		}
	}

	return true; 
}

bool check_parentheses(int p,int q) {  // 判断符号是否匹配   p和q表示起始和结束位置

	
	if (tokens[p].type != '(' || tokens[q].type != ')')//两端括号不匹配或没有括号
		return false;
	int l = p, r = q;    //判断内容中的括号是否匹配
	while (l < r)
	{
		if (tokens[l].type == '(')
		{
			if (tokens[r].type == ')')
			{
				l++, r--;
				continue;
			}

			else
				r--;
		}
		else if (tokens[l].type == ')')
			return false;
		else l++;
	}
	return true;
}

uint32_t eval(int p, int q) {
	if (p > q) {
		/*bad expression*/
		return 0;
	}
	else if (p == q) {
		/*Single token
		For now this token shoule be a number
		return the value of the number*/  //只有一个数字

		if (tokens[p].type == NUM || tokens[p].type == HEXNUM)// 十进制或十六进制
		{
			uint32_t temp;
			sscanf(tokens[p].str, "%d", &temp);//将token字符串转换为整数 存储在temp中
			return temp;
		}

		else if (tokens[p].type == REGNAME) //寄存器类型
		{
			int i;
			for (i = 0; i < 32; i++)
			{
				if (!strcmp(tokens[p].str, regfile[i])) //  比较token的字符串与寄存器数组 regfile 中的每个寄存器名
				{
					return cpu.gpr[i]._32; //  若匹配返回通用寄存器的值
				}
			}
			if (!strcmp(tokens[p].str, "$pc")) // 单独比较程序计数器
			{
				return cpu.pc;
			}
		}
		return 0;
	}
	else if (check_parentheses(p, q) == true) {
		/*the expression is surrounded by a matched pair of  parentheses
		if that is the case just throw the parentheses*/
		return eval(p + 1, q - 1);
	}
	// 判断优先级后进行运算
	else {
		/*we should do more things here*/

		int op = -1; // op = the position of operator in the token expression; 主运算符所在位置
		int dom = -2;//优先级，用于确定哪个是主运算符，dom越小优先级越高  dominant operator
		int i;
		for (i = p; i <= q; i++)
		{
			//如果有括号，优先级最高，先跳过整个括号
			if (tokens[i].type == '(')
			{
				while (tokens[i].type != ')')
					i++;
			}

			//优先级大小：OR  < AND < NOTEQ < EQ < +- < */ < (负号 指针 !)
			//优先级高的先算，所以从优先级低的开始递归，让优先级低的最后算
			//对于每种运算符类型，检查其优先级，并根据 dom 的值决定是否更新 op 和 dom

			if (tokens[i].type == 7 && dom <= 7)
			{ // OR
				op = max(op, i);
				dom = 7;
			}

			if (tokens[i].type == 6 && dom <= 6)
			{ // AND
				op = max(op, i);
				dom = 6;
			}

			if ((tokens[i].type == 5 || tokens[i].type == 1) && dom <= 5)
			{ // NOTEQ,EQ
				op = max(op, i);
				dom = 5;
			}

			if ((tokens[i].type == '+' || tokens[i].type == '-') && dom <= 4)
			{ // +-
				op = max(op, i);
				dom = 4;
			}
			if ((tokens[i].type == '*' || tokens[i].type == '/') && dom <= 3)
			{ // */
				op = max(op, i);
				dom = 3;
			}
			if ((tokens[i].type == NEG || tokens[i].type == DEREF || tokens[i].type == '!' || tokens[i].type == REGNAME) && dom <= 2)
			{ // NEG DEREF REGNAME
				op = max(op, i);
				dom = 2;
			}
		}
	
		int  op_type = tokens[op].type;

		// 递归处理两边表达式
		uint32_t  val1 = eval(p, op - 1);
		uint32_t  val2 = eval(op + 1, q);

		switch (op_type) {
		case NEG:
			return -val2;
		case DEREF:
			return mem_read(val2, 4);
		case '!':
			return !val2;
		case '+':
			return val1 + val2;
		case '-':
			return val1 - val2;
		case '*':
			return val1 * val2;
		case '/':
			if (val2 == 0) {
				printf("division can't be zero;\n");
				return 0;
			}
			return val1 / val2;
		case 1:
			return val1 == val2;
		case 5:
			return val1 != val2;
		case 7:
			return val1 || val2;
		case 6:
			return val1 && val2;
		default:
			printf("No Op type.");
			assert(0);
		}
	}
}

uint32_t expr(char *e, bool *success) {  //布尔指针succes判断是否解析成功
	if(!make_token(e)) {
		*success = false;
		return 0;
	}

	/* TODO: Insert codes to evaluate the expression. */
	// panic("please implement me");
	*success = true;
	int i;
	for (i = 0; i < nr_token; i++)  //遍历所有生成的token，nr_token是词牌数量
	{
		if (tokens[i].type == '*' && (i == 0 || (tokens[i - 1].type != NUM && tokens[i - 1].type != HEXNUM && tokens[i - 1].type != REGNAME && tokens[i - 1].type != ')')))
		{
			tokens[i].type = DEREF;//处理指针和乘号   通过前一个token不是数字类型的来判断该*为指针
		}

		if (tokens[i].type == '-' && (i == 0 || (tokens[i - 1].type != NUM && tokens[i - 1].type != HEXNUM && tokens[i - 1].type != REGNAME && tokens[i - 1].type != ')')))
		{
			tokens[i].type = NEG;//处理负数：若符号前是数字或寄存器或括号则为减号，否则为负号
		}
	}
	return eval(0, nr_token - 1);  //计算正则表达式的值
}

